#include "grammar.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>


/* Lists Functions */
void printGrammarList(grammarSymbolsList g)
{
	grammarSymbolsList l = g;
	for(; l; l = l->nextSymbol)
		printf("<%s>", l->symbolName);
}

void addGrammarSymbolsList(grammarSymbolsList *g, char symbolName[])
{
	grammarSymbolsList l = *g;
	grammarSymbolsList p = (grammarSymbolsList)malloc(sizeof(grammarSymbolElemment));
	strcpy(p->symbolName, symbolName);
	for(; l && l->nextSymbol; l = l->nextSymbol);
	if(l)	
		l->nextSymbol = p;
	else
		*g = p;
}

void printUnion(rightSideGrammarDerivation r)
{
	rightSideGrammarDerivation l = r;
	for(; l; l = l->next)
	{
		printGrammarList(l->concatDerivation);
		if(l->next)
			printf("|");
		else
			printf(";");
	}
}

void addUnion(rightSideGrammarDerivation *r, grammarSymbolsList l)
{
	rightSideGrammarDerivation p = *r;
	rightSideGrammarDerivation new = 
		(rightSideGrammarDerivation)malloc(sizeof(grammarUnionElemment));
	new->concatDerivation = l;
	for(; p && p->next; p = p->next);
	if(p)
		p->next = new;
	else
		*r = new;
}

void printGrammarDerivations(grammarDerivationsList g)
{
	grammarDerivationsList l = g;
	for(; l; l = l->next)
	{
		printf("<%s>", l->symbolName);
		printf("::=");
		printUnion(l->rDerivation);
		printf("\n");
	}
}

void addGrammarDerivation(grammarDerivationsList *g, rightSideGrammarDerivation r,
	char firstSymbolName[])
{
	grammarDerivationsList p = *g;
	grammarDerivationsList new = 
		(grammarDerivationsList)malloc(sizeof(grammarDerivationElemment));
	new->rDerivation = r;
	strcpy(new->symbolName, firstSymbolName);
	for(; p && p->next; p = p->next);
	if(p)
		p->next = new;
	else
		*g = new;
}

void removeSimpleLeftRec(grammarDerivationsList *g, char symbolName[])
{
	grammarDerivationsList p = *g;
	char newSymbolName[40];	
	strcpy(newSymbolName, symbolName);
	strcat(newSymbolName, "\'");
	for(; p && (strcmp(p->symbolName, symbolName) != 0); p = p->next);
	if(p)
	{
		rightSideGrammarDerivation r = p->rDerivation, newRSide = NULL, oldRSide = NULL;
		for(; r; r = r->next)
		{
			grammarSymbolsList newConcatDerivation = NULL, oldConcatDerivation = NULL;
			if(strcmp(r->concatDerivation->symbolName, symbolName) == 0)
			{
				grammarSymbolsList aux;
				for(aux = r->concatDerivation->nextSymbol; aux; aux = aux->nextSymbol)
					addGrammarSymbolsList(&newConcatDerivation, aux->symbolName);
				addGrammarSymbolsList(&newConcatDerivation, newSymbolName);
			}
			else
			{
				grammarSymbolsList aux;
				for(aux = r->concatDerivation; aux; aux = aux->nextSymbol)
					addGrammarSymbolsList(&oldConcatDerivation, aux->symbolName);
				addGrammarSymbolsList(&oldConcatDerivation, newSymbolName);
			}
			if(newConcatDerivation)
				addUnion(&newRSide, newConcatDerivation);
			if(oldConcatDerivation)
				addUnion(&oldRSide, oldConcatDerivation);			
		}
		if(newRSide && oldRSide)
		{
			grammarSymbolsList empty = (grammarSymbolsList)malloc(sizeof(grammarSymbolElemment));
			strcpy(empty->symbolName, "?");
			addUnion(&newRSide, empty);
			addGrammarDerivation(g, newRSide, newSymbolName);
			p->rDerivation = oldRSide;			
		}
	}
}

void subOperation(grammarDerivationsList *s1, grammarDerivationsList *s2)
{
	grammarDerivationsList p1 = *s1, p2 = *s2;
	rightSideGrammarDerivation r1;
	for(r1 = p1->rDerivation; r1; r1 = r1->next)
	{
		if(strcmp(r1->concatDerivation->symbolName, p2->symbolName) == 0)
		{
			rightSideGrammarDerivation raux1, raux2, newR = NULL;
			for(raux2 = p2->rDerivation; raux2; raux2 = raux2->next)
			{
				grammarSymbolsList newAux = NULL, laux1 = NULL, laux2 = NULL;
				for(laux2 = raux2->concatDerivation; laux2; laux2 = laux2->nextSymbol)
					addGrammarSymbolsList(&newAux, laux2->symbolName);				
				for(laux1 = r1->concatDerivation->nextSymbol; laux1; laux1 = laux1->nextSymbol)					
					addGrammarSymbolsList(&newAux, laux1->symbolName);
				addUnion(&newR, newAux);
			}
			if(newR)
			{
				rightSideGrammarDerivation newRAux = NULL, freeR = NULL;
				for(newRAux = newR; newRAux && newRAux->next != NULL; newRAux = newRAux->next);
				if(p1->rDerivation == r1)
					p1->rDerivation = newR;
				else
				{
					for(raux1 = p1->rDerivation; raux1 && raux1->next != r1; raux1 = raux1->next);					
					raux1->next = newR;										
				}
				newRAux->next = r1->next;				
			}
		}
	}
	//printUnion(p1->rDerivation);
}

void removeLeftRec(grammarDerivationsList *g)
{
	grammarSymbolsList symbolOrder = NULL, innerI = NULL, exI = NULL;
	grammarDerivationsList p = *g, innerG, exG;
	for(;p; p = p->next)
		addGrammarSymbolsList(&symbolOrder, p->symbolName);
	p = *g;
	for(innerI = symbolOrder; innerI; innerI = innerI->nextSymbol)
	{
		for(innerG = p; innerG && (strcmp(innerG->symbolName, innerI->symbolName)!=0); innerG = innerG->next);
		for(exI = symbolOrder; exI && exI != innerI; exI = exI->nextSymbol)
		{
			for(exG = p; exG && (strcmp(exG->symbolName, exI->symbolName)!=0); exG = exG->next);
			subOperation(&innerG, &exG);
		}
		
		
		removeSimpleLeftRec(&p, innerI->symbolName);
	}
}
